漫画：高并发下的 HashMap

本文由 简悦 SimpRead 转码， 原文地址 https://juejin.im/post/5a224e1551882535c56cb940

​上一期我们介绍了 HashMap 的基本原理，没看过的小伙伴们可以点击下面的链接：

漫画：什么是 HashMap？

这一期我们来讲解高并发环境下，HashMap 可能出现的致命问题。

HashMap 的容量是有限的。当经过多次元素插入，使得 HashMap 达到一定饱和度时，Key 映射位置发生冲突的几率会逐渐提高。

这时候，HashMap 需要扩展它的长度，也就是进行 Resize。

影响发生 Resize 的因素有两个：

1.Capacity

HashMap 的当前长度。上一期曾经说过，HashMap 的长度是 2 的幂。

2.LoadFactor

HashMap 负载因子，默认值为 0.75f。

衡量 HashMap 是否进行 Resize 的条件如下：

HashMap.Size >= Capacity * L**oadFactor**

1. 扩容

创建一个新的 Entry 空数组，长度是原数组的 2 倍。

2.ReHash

遍历原 Entry 数组，把所有的 Entry 重新 Hash 到新数组。为什么要重新 Hash 呢？因为长度扩大以后，Hash 的规则也随之改变。

让我们回顾一下 Hash 公式：

index = HashCode（Key） & （Length - 1）

当原数组长度为 8 时，Hash 运算是和 111B 做与运算；新数组长度为 16，Hash 运算是和 1111B 做与运算。Hash 结果显然不同。

Resize 前的 HashMap：

Resize 后的 HashMap：

ReHash 的 Java 代码如下：

/**
 * Transfers all entries from current table to newTable.
 */
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}复制代码

注意：下面的内容十分烧脑，请小伙伴们坐稳扶好。

假设一个 HashMap 已经到了 Resize 的临界点。此时有两个线程 A 和 B，在同一时刻对 HashMap 进行 Put 操作：

此时达到 Resize 条件，两个线程各自进行 Rezie 的第一步，也就是扩容：

这时候，两个线程都走到了 ReHash 的步骤。让我们回顾一下 ReHash 的代码：

假如此时线程 B 遍历到 Entry3 对象，刚执行完红框里的这行代码，线程就被挂起。对于线程 B 来说：

e = Entry3

next = Entry2

这时候线程 A 畅通无阻地进行着 Rehash，当 ReHash 完成后，结果如下（图中的 e 和 next，代表线程 B 的两个引用）：

直到这一步，看起来没什么毛病。接下来线程 B 恢复，继续执行属于它自己的 ReHash。线程 B 刚才的状态是：

e = Entry3

next = Entry2

当执行到上面这一行时，显然 i = 3，因为刚才线程 A 对于 Entry3 的 hash 结果也是 3。

我们继续执行到这两行，Entry3 放入了线程 B 的数组下标为 3 的位置，并且 e 指向了 Entry2。此时 e 和 next 的指向如下：

e = Entry2

next = Entry2

整体情况如图所示：

接着是新一轮循环，又执行到红框内的代码行：

e = Entry2

next = Entry3

整体情况如图所示：

接下来执行下面的三行，用头插法把 Entry2 插入到了线程 B 的数组的头结点：

整体情况如图所示：

第三次循环开始，又执行到红框的代码：

e = Entry3

next = Entry3.next = null

最后一步，当我们执行下面这一行的时候，见证奇迹的时刻来临了：

newTable[i] = Entry2**

e = Entry3

**Entry2.next = Entry3**

Entry3.next = Entry2

链表出现了环形！

整体情况如图所示：

此时，问题还没有直接产生。当调用 Get 查找一个不存在的 Key，而这个 Key 的 Hash 结果恰好等于 3 的时候，由于位置 3 带有环形链表，所以程序将会进入死循环！

这种情况，不禁让人联想到一道经典的面试题：

漫画算法：如何判断链表有环？

1.Hashmap 在插入元素过多的时候需要进行 Resize，Resize 的条件是

HashMap.Size >= Capacity * LoadFactor。**

**2.Hashmap 的 Resize 包含扩容和 ReHash 两个步骤，ReHash 在并发的情况下可能会形成链表环。**

—————END—————

喜欢本文的朋友们，欢迎长按下图关注订阅号程序员小灰，收看更多精彩内容